/* text.cpp
Copyright (c) 2008 Michael Zahniser
Please note the license terms (MIT license) at the end of this document.

Function definitions for the text class.

Note: A mark is only invalidated by functions that move or expand the gap.
The only functions that do either of the above directly are move_gap and reserve.
*/

#include "text.h"

#include <cstring>

using std::strlen;
using std::memmove;
using std::memcpy;



// Default constructor.
// Allocates an empty text buffer of the MINIMUM_SIZE.
text::text()
{
	init_marks();

	buffer = new char[MINIMUM_SIZE];
	bufferEnd = buffer + MINIMUM_SIZE;
	gap = buffer;
	gapEnd = bufferEnd;

	gapMark->pos = MINIMUM_SIZE;
}



// Constructor, specifying a string and optionally its length.
// If length < MINIMUM_SIZE, creates a gap at the end of the string.
text::text(const char *str, size_t length)
{
	init_marks();

	if(!length)
		length = strlen(str);

	size_t size = (length < MINIMUM_SIZE) ? MINIMUM_SIZE : length;

	buffer = new char[size];
	bufferEnd = buffer + size;
	gapMark->pos = size;

	assign(str, length);
}



// Copy constructor.
text::text(const text &t)
{
	init_marks();

	buffer = new char[t.size()];
	bufferEnd = buffer + t.size();
	gapMark->pos = t.size();

	*this = t;
}



// Destructor.
text::~text()
{
	// Clear the text first, to invalidate all marks.
	clear();

	delete [] buffer;
}



// Make this a deep copy of the given text object.
text &text::operator=(const text &t)
{
	// Check for self-assignment.
	if(&t != this)
	{
		// Only resize if my capacity is smaller than the _size_ of the
		// given text - that is, its actual bytes without the gap.
		clear();
		if(capacity() < t.size())
			reserve(t.size());

		// Copy the text, but with the gap at the end.
		memcpy(buffer, t.buffer, t.gap - t.buffer);
		memcpy(buffer + (t.gapEnd - t.buffer), t.gapEnd, t.bufferEnd - t.gapEnd);

		gap = buffer + t.size();
	}
	return *this;
}



// Copy the given string into this text object.
text &text::operator=(const char *str)
{
	assign(str, strlen(str));
	return *this;
}



// Copy the given string into this text. If you don't want to
// specify the string length, use operator=, above.
// If length < MINIMUM_SIZE, creates a gap at the end of the string.
void text::assign(const char *str, size_t length)
{
	clear();
	if(capacity() < length)
		reserve(length);

	memcpy(buffer, str, length);

	gap = buffer + length;
}



// Swap the data in two different text objects.
void text::swap(text &text)
{
	std::swap(buffer, text.buffer);
	std::swap(gap, text.gap);
	std::swap(gapEnd, text.gapEnd);
	std::swap(bufferEnd, text.bufferEnd);
}



// Use the given buffer. When this function is called, text
// becomes the owner of the given array, which must have been
// allocated usng new[].
void text::use_buffer(char *str, int length)
{
	// Trust the user not to give an invalid pointer or a length of zero.
	delete [] buffer;

	buffer = str;
	bufferEnd = str + length;

	gap = bufferEnd;
	gapEnd = bufferEnd;
}



// begin():
text::iterator text::begin()
{
	return iterator((gap == buffer) ? gapEnd : buffer, gap, gapEnd);
}



// begin() const:
text::const_iterator text::begin() const
{
	return const_iterator((gap == buffer) ? gapEnd : buffer, gap, gapEnd);
}



// end():
text::iterator text::end()
{
	return iterator(bufferEnd, gap, gapEnd);
}



// end() const:
text::const_iterator text::end() const
{
	return const_iterator(bufferEnd, gap, gapEnd);
}



// Convert an iterator into a mark.
text::mark text::make_mark(const_iterator it) const
{
	// Get the position of this mark.
	ptrdiff_t pos = it.p - buffer;

	// Check for the position in the marks list.
	std::list<MarkAnchor>::iterator markIt = gapMark;

	if(it.p >= gap)
	{
		// If we're past the gap, search forward for the insertion point.
		// We know that gapMark <= unMark <= marks.end().
		for(++markIt; markIt != unMark; ++markIt)
			if(markIt->pos >= pos)
				break;
	}
	else
	{
		// Otherwise, search backward.
		for( ; markIt != marks.begin(); --markIt)
			if(markIt->pos < pos)
			{
				++markIt;
				break;
			}
	}

	// Check whether this mark already exists. If it doesn't, create it.
	if(markIt == unMark || markIt->pos != pos)
	{
		marks.insert(markIt, MarkAnchor(pos));
		--markIt;
	}

	return mark(marks, markIt);
}



// Convert a mark into an iterator.
text::const_iterator text::make_iterator(mark mk) const
{
	if(!mk)
		return end();

	return const_iterator(buffer + mk.it->pos, gap, gapEnd);
}



text::iterator text::make_iterator(mark mk)
{
	return unconst(static_cast<const text *>(this)->make_iterator(mk));
}



// Convert the given const_iterator into a mutable iterator.
// This can only be done from non-const member functions.
text::iterator text::unconst(const_iterator it)
{
	return iterator(const_cast<char *>(it.p), const_cast<char *>(it.gap), const_cast<char *>(it.gapEnd));
}



// Get the number of bytes in the text.
size_t text::size() const
{
	return capacity() - (gapEnd - gap);
}



// Clear all data.
void text::clear()
{
	// Resize the gap to fill the buffer.
	// Erase all marks, including marks at the beginning of the file.
	iterator theEnd = end();
	move_gap(theEnd, size() + 1);
}



// Check if any data is contained in this text.
bool text::empty() const
{
	return !size();
}



// Reserve the given number of bytes.
void text::reserve(size_t bytes)
{
	// Only allow the buffer to grow, not to shrink.
	ptrdiff_t growth = bytes - capacity();
	if(growth <= 0)
		return;

	char *newBuffer = new char[bytes];
	// We still only want one gap. So, enlarge the gap, lining up everything to its left
	// with the new buffer begin, and everything to its right with the end.
	size_t leftSize = gap - buffer;
	memcpy(newBuffer, buffer, leftSize);

	size_t rightSize = bufferEnd - gapEnd;
	memcpy(newBuffer + (bytes -  rightSize), gapEnd, rightSize);

	// Change the pointers to point to the new buffer.
	gap = newBuffer + leftSize;
	bufferEnd = newBuffer + bytes;
	gapEnd = bufferEnd - rightSize;

	// Free the old buffer.
	delete [] buffer;
	buffer = newBuffer;

	// Update the marks.
	for(std::list<MarkAnchor>::iterator it = gapMark; it != unMark; ++it)
		it->pos += growth;
}



// Get the number of bytes reserved.
size_t text::capacity() const
{
	return (bufferEnd - buffer);
}



// Insert the given string to the left of the iterator.
// Returns the new position of the iterator.
// Invalidates all iterators except the one returned.
text::iterator text::insert(const char *str, size_t length, iterator it)
{
	// Move the gap to right before the iterator.
	move_gap(it);

	// Check how much capacity we need in order to insert the new string.
	size_t currentCapacity = capacity();
	size_t minimumCapacity = size() + length;

	if(currentCapacity < minimumCapacity)
	{
		// Double the capacity. But if that's not enough, enlarge it to just
		// enough to hold the given string.
		currentCapacity *= 2;
		if(currentCapacity < minimumCapacity)
			currentCapacity = minimumCapacity;

		reserve(currentCapacity);
		// Store the newly resized gap in the iterator.
		// it.gap will be updated below.
		it.gapEnd = gapEnd;
		it.p = gapEnd;
	}

	// Copy the string into the gap. The above gurantees the gap is big enough.
	memcpy(gap, str, length);
	// Update the gap pointer. Also update it's copy of the gap pointer.
	gap += length;
	it.gap = gap;
	gapMark->pos = gapEnd - buffer;

	return it;
}



// Insert the given string to the left of the iterator.
// Returns the new position of the iterator.
// Invalidates all iterators except the one returned.
text::iterator text::insert(const char *str, iterator it)
{
	return insert(str, strlen(str), it);
}



// Insert the given character to the left of the iterator.
// Returns the new position of the iterator.
// Invalidates all iterators except the one returned.
text::iterator text::insert(char c, iterator it)
{
	return insert(&c, 1, it);
}



// Delete the character to the left of the iterator.
// Does nothing if the given iterator is at the beginning.
// Returns the new position of the iterator.
text::iterator text::backspace(iterator it)
{
	// Move the gap to it and erase 1 byte.
	// backspace(begin()) will delete a mark at the beginning of the file.
	// Nothing else (aside from clear()) will accomplish this.
	move_gap(it, 1);

	return it;
}



// Delete the characters between the given iterators.
// Returns an iterator to where those characters used to be.
// Invalidates all iterators except the one returned.
text::iterator text::erase(iterator first, iterator last)
{
	// Is the current gap likely to be closer to first, or to last?
	// This determines the most efficient way to do this erasure.
	// My guess is it's closer to last. So, move the gap to the last
	// position, then expand the start of the gap backwards.

	// Get the number of bytes to delete.
	size_t bytes = last - first;

	// Move the gap to the last iterator.
	// Don't bother to move text that we plan to delete.
	move_gap(last, bytes);

	return last;
}



// Delete the character to the right of the iterator.
// Does nothing if the given iterator is at the end.
// Returns the new position of the iterator.
text::iterator text::erase(iterator it)
{
	if(it.p != bufferEnd)
	{
		// Move the gap after it and erase 1 byte.
		++it;
		move_gap(it, 1);
	}

	return it;
}



// Search the string for the first instance of the given string.
// This version specifies the search string length.
text::const_iterator text::find(const char *str, size_t length, const_iterator it) const
{
	// If we're searching for a single character, do the simpler, faster search.
	if(length == 1)
		return find(*str, it);

	// Populate the skip array.
	const char *const strEnd = str + length;

	static size_t skip[256];
	for(int i = 0; i < 256; ++i)
		skip[i] = length + 1;
	for(const char *s = str; s < strEnd; ++s)
		skip[static_cast<unsigned char>(*s)] = (strEnd - s);

	const char *const strLast = strEnd - 1;

	// First, look for the string to the left of the gap.
	const char *const beforeGap = gap - length;
	while(it.p < beforeGap)
	{
		const char *s = str;
		const char *t = it.p;
		while(*s == *t)
		{
			if(s == strLast)
				return it;
			++s;
			++t;
		}
		it.p += skip[static_cast<unsigned char>(*(it.p + length))];
	}

	// Now, search in the range straddling the gap.
	while(it.p < gapEnd)
	{
		const char *s = str;
		const char *t = it.p;
		while(*s == *t)
		{
			if(s == strLast)
				return it;
			++s;
			++t;
			if(t == gap)
				t = gapEnd;
		}
		it += skip[static_cast<unsigned char>(*(it + length))];
	}

	// Now we're clear of the gap. Search the rest of the string.
	const char *const beforeEnd = bufferEnd - length;
	while(it.p < beforeEnd)
	{
		const char *s = str;
		const char *t = it.p;
		while(*s == *t)
		{
			if(s == strLast)
				return it;
			++s;
			++t;
		}
		it.p += skip[static_cast<unsigned char>(*(it.p + length))];
	}

	// If we're now lined up with the very end, it wasn't safe to repeat
	// the above loop because *(it.p + length) is undefined.
	if(it.p == beforeEnd)
	{
		const char *s = str;
		const char *t = it.p;
		while(*s == *t)
		{
			if(s == strLast)
				return it;
			++s;
			++t;
		}
	}

	return end();
}



text::iterator text::find(const char *str, size_t length, iterator it)
{
	return unconst(find(str, length, const_iterator(it)));
}



// Search the string for the first instance of the given string.
text::const_iterator text::find(const char *str, const_iterator it) const
{
	return find(str, strlen(str), it);
}



text::iterator text::find(const char *str, iterator it)
{
	return unconst(static_cast<const text *>(this)->find(str, const_iterator(it)));
}



// Search the string for the given character.
text::const_iterator text::find(char c, const_iterator it) const
{
	if(it.p < gap)
	{
		do {
			if(*(it.p) == c)
				return it;
			++it.p;
		} while(it.p < gap);

		// Now, it.p == gap.
		it.p = gapEnd;
	}

	while(it.p < bufferEnd)
	{
		if(*(it.p) == c)
			return it;
		++it.p;
	}

	// Now, it.p == bufferEnd.
	return it;
}



text::iterator text::find(char c, iterator it)
{
	return unconst(find(c, const_iterator(it)));
}



// Search backward for the first instance of the given string.
// This version specifies the search string length.
text::const_iterator text::rfind(const char *str, size_t length, const_iterator it) const
{
	// If we're searching for a single character, do the simpler, faster search.
	if(length == 1)
		return rfind(*str, it);

	// Make sure the iterator is far enough from the end that the string
	// beginning at the iterator is as long as the search string.
	const_iterator lastValidIt = end();
	lastValidIt -= length;
	if(it > lastValidIt)
		it = lastValidIt;

	// Populate the skip array.
	const char *const strEnd = str + length;

	static size_t skip[256];
	for(int i = 0; i < 256; ++i)
		skip[i] = length + 1;
	for(const char *s = strEnd; s-- > str; )
		skip[static_cast<unsigned char>(*s)] = (s - str) + 1;

	const char *const strLast = strEnd - 1;

	// First, look for the string to the right of the gap.
	while(it.p > gapEnd)
	{
		const char *s = str;
		const char *t = it.p;
		while(*s == *t)
		{
			if(s == strLast)
				return it;
			++s;
			++t;
		}
		it.p -= skip[static_cast<unsigned char>(*(it.p - 1))];
	}

	// Now, search in the range straddling the gap.
	const char *beforeGap = gap - length;
	while(it.p > beforeGap)
	{
		const char *s = str;
		const char *t = it.p;
		while(*s == *t)
		{
			if(s == strLast)
				return it;
			++s;
			++t;
			if(t == gap)
				t = gapEnd;
		}
		it -= skip[static_cast<unsigned char>(*(it - 1))];
	}

	// Now we're clear of the gap. Search the rest of the string.
	while(it.p > buffer)
	{
		const char *s = str;
		const char *t = it.p;
		while(*s == *t)
		{
			if(s == strLast)
				return it;
			++s;
			++t;
		}
		it.p -= skip[static_cast<unsigned char>(*(it.p - 1))];
	}

	// If we're now lined up with the very beginning, it wasn't safe to repeat
	// the above loop because *(it.p - 1) is undefined.
	if(it.p == buffer)
	{
		const char *s = str;
		const char *t = it.p;
		while(*s == *t)
		{
			if(s == strLast)
				return it;
			++s;
			++t;
		}
	}

	return end();
}



text::iterator text::rfind(const char *str, size_t length, iterator it)
{
	return unconst(rfind(str, length, const_iterator(it)));
}



// Search backward for the first instance of the given string.
text::const_iterator text::rfind(const char *str, const_iterator it) const
{
	return rfind(str, strlen(str), it);
}



text::iterator text::rfind(const char *str, iterator it)
{
	return unconst(static_cast<const text *>(this)->rfind(str, const_iterator(it)));
}



// Search backward for the given character.
text::const_iterator text::rfind(char c, const_iterator it) const
{
	// Allow the end iterator to be passed as an argument.
	if(it == end())
		--it;

	if(it.p >= gapEnd)
	{
		do {
			if(*(it.p) == c)
				return it;
			--it.p;
		} while(it.p >= gapEnd);

		// Now, it.p == gapEnd - 1.
		it.p = gap - 1;
	}

	while(it.p >= buffer)
	{
		if(*(it.p) == c)
			return it;
		--it.p;
	}

	it.p = bufferEnd;
	return it;
}



text::iterator text::rfind(char c, iterator it)
{
	return unconst(rfind(c, const_iterator(it)));
}



std::ostream &operator<<(std::ostream &out, const text &t)
{
	out.write(t.buffer, static_cast<std::streamsize>(t.gap - t.buffer));
	out.write(t.gapEnd, static_cast<std::streamsize>(t.bufferEnd - t.gapEnd));
	return out;
}



// Read until the end of the input.
std::istream &operator>>(std::istream &in, text &t)
{
	t.clear();

	while(true)
	{
		in.read(t.gap, static_cast<std::streamsize>(t.gapEnd - t.gap));
		t.gap += in.gcount();

		// If we've reached the end of input, return.
		if(!in)
			break;

		// Otherwise, double the buffer size and try again.
		t.reserve(2 * t.capacity());
	}

	return in;
}



// Initialize the mark list.
void text::init_marks()
{
	// TODO: Allocate the mark anchors in a shared pointer.
	gapMark = marks.insert(marks.end(), MarkAnchor(-2));
	unMark = marks.insert(marks.end(), MarkAnchor(-2));
}



// Move the gap to the given position. Update the iterator to point to
// the end of the gap. Also increase the size of the gap by the given amount.
// This is the _only_ function allowed to move or expand the gap, and thus the
// only function that must manage marks. (Adding characters, i.e. filling the
// gap, does not invalidate any marks.)
void text::move_gap(iterator &it, size_t sizeIncrease)
{
	// Move the gap to the iterator's position. An iterator that is "on" the
	// gap should in fact point to the character right after the gap, since
	// insert() inserts before the given iterator.
	if(it.p != gapEnd)
	{
		// Find the width of the gap. If it is empty, we don't need to move text,
		// but we still need to move the gap mark.
		size_t gapWidth = (gapEnd - gap);
		// Update the gap mark position.
		gapMark->pos = it.p - buffer;
		std::list<MarkAnchor>::iterator newGapIt = gapMark;

		if(it.p < gap)
		{
			// Shift text to the right (i.e. move the gap to the left).
			ptrdiff_t bytesToMove = gap - it.p;
			if(gapWidth && bytesToMove > 0)
				memmove(gapEnd - bytesToMove, it.p, bytesToMove);

			// Update the marks.
			while(newGapIt != marks.begin())
			{
				--newGapIt;
				if(newGapIt->pos < gapMark->pos)
				{
					++newGapIt;
					break;
				}
				newGapIt->pos += gapWidth;
			}

			// Update the iterator to point to the end of the gap.
			it.p += gapWidth;
			gapMark->pos += gapWidth;
		}
		else
		{
			// Shift text to the left (i.e. move the gap to the right).
			// If the gap size is increasing, don't bother to copy the
			// text that is going to be deleted (subsumed into the gap).
			ptrdiff_t bytesToMove = (it.p - gapEnd) - sizeIncrease;
			if(gapWidth && bytesToMove > 0)
				memmove(gap, gapEnd, bytesToMove);

			// Update the marks.
			while(++newGapIt != unMark)
			{
				if(newGapIt->pos >= gapMark->pos)
					break;
				newGapIt->pos -= gapWidth;
			}
		}

		marks.splice(newGapIt, marks, gapMark);
		gapEnd = it.p;
		gap = gapEnd - gapWidth;
	}

	// Now, it.p == gapEnd. Increase the gap width by the given amount.
	if(sizeIncrease)
	{
		gap -= sizeIncrease;

		// Invalidate all marks in the range (gap - sizeIncrease, gap).
		// Keep examining the MarkAnchor right before gapMark until either
		// nothing is there, or the next anchor is not in the deleted range.
		ptrdiff_t beginGap = gap - buffer;
		while(gapMark != marks.begin())
		{
			std::list<MarkAnchor>::iterator it = gapMark;
			--it;
			if(it->pos <= beginGap)
				break;

			// This mark has been invalidated. Set its position to -1, and
			// move it out of the main list into the unMark section.
			it->pos = -1;
			marks.splice(marks.end(), marks, it);
		}

		// If we can't increase the gap that much, increase it by as much as possible.
		if(gap < buffer)
			gap = buffer;
	}

	// Make sure the iterator's data is up to date.
	it.gap = gap;
	it.gapEnd = gapEnd;
}



// Below are the functions for text::mark.
text::mark::mark()
	: marks(NULL)
{
}



text::mark::mark(const mark &mk)
	: marks(NULL)
{
	*this = mk;
}



text::mark::~mark()
{
	release();
}



text::mark &text::mark::operator=(const mark &mk)
{
	release();

	marks = mk.marks;
	if(marks)
		it = mk.it;

	retain();

	return *this;
}



// Check whether this mark is valid.
bool text::mark::operator!() const
{
	// This mark is not valid if it does not refer to a mark anchor,
	// or if the anchor it refers to has been deleted.
	return (!marks || it->pos < 0);
}



bool text::mark::operator==(const mark &mk) const
{
	// If the position is invalid, all comparisons return false.
	return (it->pos >= 0 && mk.it->pos >= 0 && it->pos == mk.it->pos);
}



bool text::mark::operator<(const mark &mk) const
{
	// If the position is invalid, all comparisons return false.
	return (it->pos >= 0 && mk.it->pos >= 0 && it->pos < mk.it->pos);
}



void text::mark::retain()
{
	if(marks)
		++it->count;
}



void text::mark::release()
{
	if(marks)
		if(!--it->count)
			marks->erase(it);
}



// This constructor is accessible to the text class.
text::mark::mark(std::list<MarkAnchor> &marks, std::list<MarkAnchor>::iterator it)
	: it(it), marks(&marks)
{
	retain();
}



// Below are the functions for text::iterator.

// iterator default constructor:
text::iterator::iterator()
{
}



// iterator promotion:
// Implicit conversion from an _it. Used by the _it base class when the
// return type must be promoted to iterator.
text::iterator::iterator(char *p, char *gap, char *gapEnd)
	: m_it(p, gap, gapEnd)
{
}



// Below are the functions for text::const_iterator.

// const_iterator default constructor:
text::const_iterator::const_iterator()
{
}



// const_iterator conversion from iterator:
text::const_iterator::const_iterator(const text::iterator &it)
	: c_it(it.p, it.gap, it.gapEnd)
{
}



// const_iterator private constructor:
text::const_iterator::const_iterator(const char *p, const char *gap, const char *gapEnd)
	: c_it(p, gap, gapEnd)
{
}



/* Copyright (c) 2008 Michael Zahniser

Permission is hereby granted, free of charge, to any person
obtaining a copy of this software and associated documentation
files (the "Software"), to deal in the Software without
restriction, including without limitation the rights to use,
copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the
Software is furnished to do so, subject to the following
conditions:

The above copyright notice and this permission notice shall be
included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
OTHER DEALINGS IN THE SOFTWARE. */

